To recycle data mapping structures or data structures, conventional controllers in solid-state drives follow a processor-intensive and time-consuming multi-step process to create a list of mapping structures or data structures to move prior to a block erasure operation. The list is created by either searching a physical erasure block for valid data or by searching a cached mapping structure for valid data located in the target erasure block.
To conventionally search the physical erasure block, the pages of the block within a flash device are read and a list of valid and stale candidates is created. A next step checks the candidates against a current first or prior level map for validity. The data associated with the valid entries is read from the flash device and moved to a new location within the same or another flash device. After the move is complete, the mapping structures are updated. Besides being slow, the conventional search techniques also consume appreciable bandwidth of the flash device to the detriment of a user.
To conventionally search a cached mapping structure for valid data located in the erasure block, each mapping entry is read and examined by a processor to look for a matching address of the erasure block to be recycled. The data associated with the valid entries is read from the flash device and moved to a new location within the same or another flash device. After the move is complete, the mapping structures are updated. If the mapping structures only have a single level of depth, the size of the map is large and the latter technique of searching the physical erasure block directly is more efficient and less disruptive to normal map operations.